A large factor in TCP's widespread use is its ability to utilize a network bottleneck, adapting to changes in offered load or available bandwidth. However, studies have shown that TCP's ability to share a bottleneck fairly and efficiently decreases as the number of flows increases. The performance of TCP becomes significantly degraded when the number of active TCP flows exceeds the network's bandwidth-delay product measured in packets. When the TCP sender's congestion window becomes less than 4 packets, TCP is no longer able to recover from a single packet loss since Fast-Retransmit needs at least 3 duplicate acknowledgments (ACKs) to get triggered. Thus, windows below 4 packets are not amenable to the fast retransmission feature of TCP and a single packet loss will send the connection into timeout. When fast retransmission fails, TCP falls into a conservative retransmission timeout of a second or more. Packet losses therefore affect data transfer delays in two ways: (1) by decreasing TCP's window size and sending rate, and (2) by forcing TCP into timeouts. This is because TCP adjusts its window size to reflect network conditions. Each time TCP decides that the network has discarded a packet, it cuts its window by half.
High loss rates in TCP/IP networks indicate that there is an excess of traffic and that the network has insufficient buffering or bandwidth capacity. To relieve congestion, the network has to drop many packets. However, dropping too many packets tends to penalize TCP users, forcing them into long timeout periods. Also, with inadequate buffering, TCP connections will tend to keep the buffers full and the resulting packet losses will force many of the connections into timeout. As link utilization grows, premature loss may occur long before full bottleneck utilization is achieved due to the bursty nature of TCP traffic. In addition, most TCP flows today can be characterized as short-lived flows. The fast retransmission feature of TCP requires a window size of several packets in order to work and short-lived flows often never achieve a large enough window size to be able to recover from a packet loss without entering timeout. One way to solve this problem is to provide routers with not just one round-trip time of buffering, but buffering proportional to the total number of active flows. P. Morris, “TCP Behavior with Many Flows,” IEEE Int'l Conf. on Network Protocols, Atlanta, Ga., October 1997, pp. 205-211 suggests that systems implement ten times as many buffers as flows. Large buffers should be possible in routers since the cost of memory is dropping rapidly. Many router vendors adopt the “one round-trip time” buffering approach. Although this is a step in the right direction, this only addresses the link utilization problem, but not the packet loss problem.
Even though adequate buffering proportional to the total number of active flows is required to support high number of TCP flows, the combination of adequate buffering and active queue management based on random early detection (RED) provides support to a large number of flows attempting to use full link bandwidth. This combination allows high link utilization and eliminates the possibility of degradation or collapse in link utilization due to excessive window size limits set by end users. The basic idea behind active queue management schemes such as those described in U.S. patent application Ser. No. 09/455,445, filed December 1999, and S. Floyd and V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance,” IEEE/ACM Trans. on Networking, Vol. 1, No. 4, August 1993, pp. 397-413, is to detect incipient congestion early and to convey congestion notification to the end-systems, allowing them to reduce their transmission rates before queues in the network overflow and excessive packet loss occurs.
Most RED schemes maintain an average of the queue length which they use together with a number of queue thresholds to detect congestion. RED schemes drop incoming packets in a random probabilistic manner where the probability is a function of recent buffer fill history. The objective is to provide a more equitable distribution of packet loss, avoid the synchronization of flows, and at the same time improve the utilization of the network. The setting of the queue thresholds in RED schemes is problematic because the required buffer size (and consequently queue thresholds) for good sharing among TCP connections is dependent on the number of TCP connections using the buffer. To keep latency at the router low, it may be desirable to set the thresholds low. But setting it too low will cause many timeouts (when the number of connections is large) which drastically degrade the latency perceived by the user. On the other hand, setting the thresholds too high unnecessarily increases the latency when operating with a small number of connections. This means the setting of the thresholds should not be done in an ad hoc manner but should also be tied to the number of active connections sharing the buffer. The danger of not tying the RED thresholds (and buffer size) to the number of active connections is that, for example, a RED queue (as described in S. Floyd and V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance,” IEEE/ACM Trans. on Networking, Vol. 1, No.4, August 1993, pp. 397-413) operating with a large number of connections can cause the average queue size to exceed the maximum RED threshold, causing the router to operate as a drop-tail router and resulting in high packet loss rates and TCP timeouts.
In view of the foregoing, it would be desirable to provide a technique for network queue management which overcomes the above-described inadequacies and shortcomings. More particularly, it would be desirable to provide a technique for dynamically allocating buffers in proportion to the number of active TCP connections in an efficient and cost effective manner.